# 经典的LCS问题
#   c  b  a  b  a  d
# d
# a
# b
# a
# c
# 一、公共子序列问题
# 矩阵元素表示s1[:i]和s2[:j]的公共子序列
# if i < 0 or j < 0: 0
# if s1[i] == s2[j]: d[i-1][j-1] + 1
# else: max(d[i-1][j], d[i][j-1])
# 二、公共字串问题
# 需要连续
# if i < 0 or j < 0: 0
# if s1[i] == s2[j]: d[i-1][j-1] + 1
# else: 0
# max(d[i][j])
def max_substr(s1: str, s2: str) -> str:
    """
    最长公共字串
    :param s1:
    :param s2:
    :return:
    """
    d = {}
    for i in range(len(s1)):
        for j in range(len(s2)):
            if s1[i] != s2[j]:
                continue
            if (i - 1, j - 1) not in d:
                d[(i, j)] = s1[i]
            else:
                d[(i, j)] = d[(i - 1, j - 1)] + s1[i]
    return max(d.values(), key=len)


assert max_substr('cbabad', 'dababc') == 'bab'
